\usepackage{listings}
\lstset{language=Java,
        basicstyle=\small}

\usepackage{graphicx}
\usepackage{hyperref}
\mode<article>{\usepackage{fullpage}}

\hypersetup{
  colorlinks=true,
  urlcolor=blue,
  linkcolor=black
}

\title{Lecture Seven -- Maps, Hashing, and Sets}
\author{Matt Bone}
\date{\today}

\begin{document}

\mode<article>{\maketitle}
\tableofcontents
\mode<article>{\pagebreak}
\mode<presentation>{\frame{\titlepage}}
\mode<article>{\setlength{\parskip}{.25cm}}
\mode<all>{\bibliographystyle{abbrvnat}}

\section{Maps}

\subsection{Python Dictionaries}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Python Dictionaries}}
  Most of you have spent time with Python.  In Python we have dictionaries:

  \begin{lstlisting}
    my_map = dict()
    my_map['bikes'] = 4
    my_map['working bikes'] = 0 
  \end{lstlisting}

\end{frame}

Dictionaries in Python let us associate one value with another.
You've probably seen the association of a string with some object
(thus the name dictionary), but really we can associate any object
(called the \emph{key}) with any other object (called the
\emph{value}).

Python dictionaries are an example of the map data structure.  Maps
let us look up the values with the corresponding key.  Sometimes maps
are called and thought of has \emph{lookup tables} or simply
\emph{tables}.


\subsection{Maps in Java}
Java has maps, too.  As with most of our data structures we can look
at the interface
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/Map.html}{java.util.Map}.

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Using Maps in Java}}

  Notice in the \texttt{Map} interface we can, just like Python, associate
  any two types of objects:
  \begin{lstlisting}
    Map<String, Integer> my_map = 
      new HashMap<String, Integer>();
    my_map.put("bikes", 4);
    my_map.put("working bikes", 0);
  \end{lstlisting}

\end{frame}

However, we do see some of the differences between Python and Java
here.  As we've seen with lists, the maps in Java can be given extra
type information.  So, the types of the keys and the types of the
values can be specified, and the map can remain homogeneous.  




\section{Hashing}
Though there are several techniques for implementing a map, but the
most common is hashing.

\subsection{Number please}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Number please}}

  Conceptually hashing is quite simple.  We have an arbitrary structure,
  and we ask it for a number.  
\end{frame}
The idea is the same as that of a file checksum.  The number should be
deterministic (same number when we ask the structure multiple times,
different number for non-equivalent structures).


\subsection{Hashing in Java}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Object hash themselves}}
  \mode<presentation>{If we look again at the 
    \href{http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html}{java.lang.Object}
    class, we'll see \texttt{hashCode} the method.}
\end{frame}
  
In Java and many other OO-languages, objects are responsible for generating
their own number or hash code. Looking back at the 
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html}{java.lang.Object}
class, we see that, like the \texttt{equals} method,
every object has a \texttt{hashCode} method.  


\subsection{Hashing and Maps}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Hashing and Maps}}
  After understanding hashing, we can see how it lets us map
  one object to another.
\end{frame}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{From Numbers to Indices}}
  \href{http//java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html}{java.util.HashMap}s 
  are implemented with arrays, and the basic process for storing a key/value pair 
  in this kind of maps is as follows:
  \begin{enumerate}
    \item Retrieve the key's hash code
    \item Convert this key into a suitable array index
    \item Store the value in that index OR
    \item Take appropriate collision handling steps
  \end{enumerate}
\end{frame}


\subsection{Hashing Functions}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Bad Hashing Functions}}
  \begin{lstlisting}
    public int hashCode() { return -1; }
  \end{lstlisting}  
  This hash function will actually work, but as we will see in the collisions
  section, it would yield very poor performance.\cite{goetz03:hashing}

\end{frame}

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Good Hashing Functions}}
  A better \texttt{hashCode} implementation relies on the underlying objects:
  \begin{lstlisting}
    public class BankAccount {
      public int hashCode() { 
        return this.accountNumber * 31 
          + this.accountName.hashCode(); 
      }
    }
  \end{lstlisting}  

\end{frame}

Hashing functions are a very complex topic, and those interested in
creating truly brilliant hashing functions should study some number
theory and refer to Cormen's text on algorithms and Knuth's seminal
work ``The Art of Computer Programming''.  In general, we would like to
approximate \emph{simple uniform hashing}, meaning that every object
(keys) is equally likely to hash to a given space in the underlying array
regardless of the size or capacity of the
array\cite[pg 229]{cormen00:algo}.  As a caution, in many algorithms
texts a hashing function is supposed to generate an index that is
suitable for the underlying array (i.e. in those bounds).  In Java,
though, the hashing logic is split into two parts.  Objects are asked
for their integer hashcode, and then the hash map implementation is
responsible for converting this integer into an appropriate index.  At
first glance we may just mod the hashcode with the array size, and
while this will work, having an array size that is a power of two
could then lead to many collisions.  A better choice would be a prime
array size, but this can cause memory to be allocated wastefully (some
OSes allocate memory in $2^n$ sized chunks).  While there are ways 
around both of these problems, the point is that there are many complexities
to consider.  

If you find through profiling or benchmarking that your hash map is
running close to the worst case $O(n)$, it may be time to consult some
algorithms texts and carefully consider your hashing functions.
However, in Java we can often abstract these complexities by standing
on the shoulders of giants; we simply generate hashcodes that depend
on the hashcodes of the objects' properties.  The assumption is that
the hashcodes for those underlying properties have been implemented
thoughtfully.  In this back account example, we simply rely on the
underlying account number (an int) and hash code of the account name
(a String).

It is important that the hashing be deterministic; for example, it
should not depend on the system time.  Also, if two objects are
logically equivalent, they should share the same hash code.  Realize
that the hashcode is not a global unique identifier, and two objects
may have the same one.

\subsection{Performance}
With well chosen hash functions, it is reasonable to assume that maps
implemented with hashing run at $O(1)$ for insertions, removals and
deletions on average.

Conceptually similar to `indexing' from the database world, hashing is
one technique to improve the performance of a program.  When you have
information, you can look it up with a hash function.  If you know all
the possible keys ahead of time, then you can hash everything
perfectly, and have a lookup table akin to an array (aka direct
addressing).

Memoiziation (saving the results of a computation) is another
technique.  With respect to hashing, one may want to memoize the
hashCode method (but we must also keep track of when the object is
changed and `dirty').

\section{Collisions}

\subsection{Introduction}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Collisions: Introduction}}
  Suppose we are calculating array indices with $hash\%tableSize$ and
  suppose our $tableSize$ (the array size) is $8$.  If we'd like to
  store $3$ objects with hashcodes of $16$, $32$ and $64$, we have a
  problem.

  This is called a collision, and there are several techniques to
  solving the problem.
\end{frame}

\subsection{Avoiding Collisions}

Before we even think about collision handling, we should examine the
ways in which we can avoid it.  Ideally, we'd like no collisions
because a hash table that assured no collisions would run at $O(1)$
for insertions, lookups, and deletions.  

\subsubsection{Choosing a Table Size}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Choosing a Table Size}}
  When we re-size our array we may want to carefully choose the size of
  the array.
\end{frame}
Having an array that is larger than the any hash code that we ever
encounter is certainly not a good strategy because the entries on the
large side of the array will never be used.  (Though this problem
really has more to do with our hashing function).

Also, consider the a hash table size of capacity 10.  Now, every hash
code that ends with a zero will wind up the the same spot.  Because of
this, some libraries insist that hash table capacities be primes or
even double primes.\cite{weiss07:data_struc_algos}

\subsubsection{Loading Factor and Rehashing}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Loading Factor and Rehashing}}
  The load factor is $numOfItemsInTable/capacity$.

  As the load factor of a hash table increases, so too does the likelihood
  of a collision.  Usually our hash tables have a fixed load factor, and when
  this is reached, a new larger array is created and all the old items are
  rehashed.
\end{frame}


\subsection{Collision Strategy: Chaining}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Collision Strategy: Chaining}}
  
  \mode<presentation>{Every item in the array is a linked list}

\end{frame}
In the chaining approach, linked lists of values are stored in the
array instead of the values themselves.  Items are added to the end of
the list, and this solves the collision problem.  However, when
retrieving an object, the list must be searched linearly.  Ultimately
this makes retrieval an $O(n)$ operation in the worst case.

\subsection{Collision Strategy: Open Address Hashing}
In open address hashing, we do not use a second data structure such as
a linked list.  Rather, all key/value pairs are stored directly in the
array underlying the map.  When a collision occurs, however, the
array is searched for an empty slot according to some probe sequence\cite[pg 239]{cormen00:algo}.
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Collision Strategy: Open Address Hashing}}
  A linear probe sequence simply means that we keep searching the the
  array linearly until we find an empty slot. As before, this
  can make retrieval an $O(n)$ operation.
\end{frame}
One benefit of open address hashing however is, just as with the
dynamic list, we are not following chains of references, and the
array is contiguous in memory.

\subsubsection{Primary Clustering}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Primary Clustering}}

  \mode<presentation>{Clusters == Bad}

\end{frame}
With open address hashing, we can get clusters of keys in our array.
This is bad, and the problem tends to snowball.  The larger the
cluster, the more likely the next insertion will end up in that
cluster (and thus we lose our ideal of uniform hashing).  Different probe
sequences attempt to solve the problem.    One technique is to use a
quadratic probe sequence, calculating the next probed position in the
array based off the square of the currently probed position. 

Another technique is \emph{double hashing}.  If a collision occurs, we
can run a second hash function to determine the `offset'.


\subsubsection{Removal}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Removal in Open Address Hashing}}

  \mode<presentation>{What if you want to remove an object that is surrounded
  on both sides in the array?}
  
\end{frame}
One problem with open address hashing is removal.  Assume we are using
a linear probe sequence.  If we want to remove an object in the array
we do not know if there are objects further down the array that were
intended or hashed to spots further up the array.  Thus, we cannot
simply remove the object, because the linear probe would then cease to work.
Instead, we must insert some sort of sentinel value.

\section{Sets}

\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Sets}}

  \mode<presentation>{As defined by the 
    \href{http://java.sun.com/j2se/1.4.2/docs/api/java/util/Set.html}{Set interface},
    sets are collections without duplicates.}
\end{frame}

\subsection{Hashing: Not just for Maps}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Hashing: Not just for Maps}}

  Hashing is also useful for other things.  One of these in a set.  
  We can implement a set with the techniques we've just studied.

\end{frame}
The set interface is implemented by 
\href{http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashSet.html}{java.util.HashSet} 
with a hashing backend.

\subsection{Subsets}
We can use the \texttt{containsAll} method in the set interface to
determine if one set is a subset of another.\cite{java_tut_sets}
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Subsets}}
  \begin{lstlisting}
    Set<Integer> set1; //contains 7, 5, 9
    Set<Integer> set2; //contains 10, 11, 7, 8, 5, 9

    set1.containsAll(set2); //false, set1 not a subset 
                            //of set2
    set2.containsAll(set1); //true, set2 is a subset 
                            //of set1
  \end{lstlisting}
\end{frame}


\subsection{Unions}
We can use the \texttt{addAll} method in the set interface to
compute the union of two sets.
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Unions}}
  \begin{lstlisting}
    Set<Integer> set1; //contains 7, 5, 9
    Set<Integer> set2; //contains 6, 8

    set1.addAll(set2); //set 1 now contains the union 
                       //of set1 and set2:
                       // 5, 6, 7, 8, 9
  \end{lstlisting}
\end{frame}
Unfortunately \texttt{addAll} is an operation with side effects, and the original
sets are not maintained.  To do this without destroying the original sets,
you must first make copies.\cite{java_tut_sets}

\subsection{Intersection}
We can use the \texttt{retainAll} method in the set interface to
compute the intersection of two sets.
\begin{frame}[fragile]
  \mode<presentation>{\frametitle{Intersection}}
  \begin{lstlisting}
    Set<Integer> set1; //contains 7, 5, 9
    Set<Integer> set2; //contains 5, 6, 8

    set1.retainAll(set2); //set 1 now contains the 
                          //intersection of set1 
                          //and set2:
                          //5
  \end{lstlisting}
\end{frame}
Unfortunately \texttt{retainAll} is an operation with side effects, and the original
sets are not maintained.  To do this without destroying the original sets,
you must first make copies.\cite{java_tut_sets}

\mode<all>{\bibliography{sources}}

\end{document}
